// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-26 17:16
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.ArraysTrain.preFixTrain;

import java.util.HashMap;
import java.util.Map;

public class NumSubmatrixSumTarget {
    /**
     * 元素和为目标值的子矩阵数量
     * 构建二维前缀和 + 枚举子矩阵
     */
    public int numSubmatrixSumTargetT(int[][] matrix, int target) {
        /*-----构建二维前缀和-----*/
        int n = matrix.length, m = matrix[0].length, res = 0;
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            }
        }
        /*-----枚举子矩阵-----*/
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int p = 1; p <= i; p++) {
                    for (int q = 1; q <= j; q++) {
                        if (sum[i][j] - sum[p - 1][j] - sum[i][q - 1] + sum[p - 1][q - 1] == target) {
                            res++;
                        }
                    }
                }

            }
        }
        return res;
    }

    /*-----优化枚举 + Hash查找-----*/
    public int numSubmatrixSumTarget(int[][] mat, int t) {
        int n = mat.length, m = mat[0].length;
        /*-----构建二维前缀和-----*/
        int[][] sum = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }
        /*-----优化枚举-----*/
        int ans = 0;
        for (int top = 1; top <= n; top++) {
            for (int bot = top; bot <= n; bot++) {
                /*-----固定上下边界，移动左右边界-----*/
                int cur = 0;
                Map<Integer, Integer> map = new HashMap<>();
                for (int r = 1; r <= m; r++) {
                    /*-----求取当前固定上下边界移动左右边界的矩形元素之和-----*/
                    cur = sum[bot][r] - sum[top - 1][r];
                    if (cur == t) {
                        ans++;
                    }
                    /*-----子矩阵获取------*/
                    if (map.containsKey(cur - t)) {
                        ans += map.get(cur - t);
                    }
                    /*-----更新Hash表元素-----*/
                    map.put(cur, map.getOrDefault(cur, 0) + 1);
                }
            }
        }
        return ans;
    }
}
